package _go

/*56. 合并区间
难度
中等

1216

收藏

分享
切换为英文
接收动态
反馈
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。



示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。


提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
*/

func merge(intervals [][]int) [][]int {
	n := len(intervals)
	if n <= 1 {
		return intervals
	}
	//先对整个数组排序
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	//定义一个动态的遍历常数
	forCount := n - 1
	for i := 0; i < forCount; i++ {
		//判断是否需要合并
		if intervals[i][1] >= intervals[i+1][0] {
			//将不变的数组合并到前边
			intervals[i][1] = max(intervals[i][1], intervals[i+1][1])
			//切割掉被合并的数组
			intervals = append(intervals[:i+1], intervals[i+2:]...)
			//因为切割掉了一个数组  整体循环次数要减1
			i++
			forCount--
		}
	}
	return intervals
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
